#include <stdio.h>


int searchInsert(int* nums, int numsSize, int target) {
    int s=0,e=numsSize-1,m;
    while( s <= e ) {
        m=(s+e)/2;
        if( nums[m] == target )
            return m;
        else if( nums[m] < target ){
            s=m+1;
        }else{
            e=m-1;
        }
    }
    return s;
}

int searchInsert2(int* nums, int numsSize, int target) {
    int s=0,e=numsSize-1,m;
    while( s <= e ) {
        m=s+(e-s)/2;
        if( nums[m] < target ){
            s=m+1;
        }else{
            e=m-1;
        }
    }
    return s;
}
int searchInsert3(int* nums, int numsSize, int target) {
    int s=0,e=numsSize-1,m;
    while( s <= e ) {
        m=s+(e-s)/2;
        if( nums[m] <= target ){
            s=m+1;
        }else{
            e=m-1;
        }
    }
    return e;
}
int main(){
    int a[]={1,1,2,2,2,2,2,2,3,3,3,3,3,3,5,6};
    printf( "%d\n",searchInsert3( a, sizeof(a)/sizeof(int), 2 ) );
    return 0;
}
